package com.wrial.kind.dp;
/*
 * @Author  Wrial
 * @Date Created in 10:01 2020/8/17
 * @Description  编辑距离
 * 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
        你可以对一个单词进行如下三种操作：
        插入一个字符
        删除一个字符
        替换一个字符
 */

public class MinDistance {

    /**
     * 使用动态规划，因为word2是固定的，因此以word2为列，以word1位行做dp
     * 1.如果匹配，不用进行额外操作  word1.charAt(x-1) == word2.charAt(y-1)
     * 2.如果不匹配，进行增/删/改，选一个需要步骤最小的，然后+1写入dp[i][j]
     */
    public static int minDistance(String word1, String word2) {
        int x = word1.length();
        int y = word2.length();
        int[][] dp = new int[x + 1][y + 1]; //需要加上空串的情况
        // x=0 时 word1为空串，只能增添  x=0 y=0 表示都是空串，那就不用改，也就为默认值0
        for (int i = 0; i <= y; i++) {
            dp[0][i] = i;
        }
        //y=0 时，也就是前i个进行删除多少次为空串
        for (int i = 0; i <= x; i++) {
            dp[i][0] = i;
        }

        for (int i = 1; i <= x; i++) {
            for (int j = 1; j <= y; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //增删改后需要+1
                    dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                }
            }
        }

        return dp[x][y];
    }

    public static void main(String[] args) {
        minDistance("horse", "ros");
    }
}
